/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-05-22
 * Time: 20:08
 */
//class ListNode {
//    int val;
//    ListNode next = null;
//    public ListNode(int val){
//        this.val=val;
//    }
//}
public class Solution2 {
    /**
     *
     * @param head1
     * @param head2
     * @return 返回合并后新链表的头节点
     */
    public ListNode merge(ListNode head1,ListNode head2){
        ListNode res=new ListNode(-1);
        ListNode cur=res;
        if(head1==null){
            return head2;
        }
        if(head2==null){
            return head1;
        }
        while (head1!=null && head2!=null){
            if(head1.val<head2.val){
                cur.next=head1;
                head1=head1.next;
            }else{
                cur.next=head2;
                head2=head2.next;
            }
            cur=cur.next;
        }
        if(head1==null){
            cur.next=head2;
        }
        if(head2==null){
            cur.next=head1;
        }
        return res.next;
    }
    
    /**
     *
     * @param head
     * @return 时间复杂度 O(nlog2n)  归并的时间复杂度
     *         空间复杂度O(log2n) ,递归栈的深度最坏为O(log2n)
     *
     */
    public ListNode sortInList (ListNode head) {
        //递归划分到只有一个节点时,本身就是有序的，返回去和另一个链表的另一个节点合并
        if(head==null || head.next==null){
            return head;
        }
        //方法二，使用归并排序对链表排序时最优解
        //使用快慢指针找到中间节点，然后一直递归划分成两个子链表，直到两个子链表都只有一个节点，然后就开始合并
        ListNode fast=head.next.next;
        ListNode slow=head;
        ListNode mid=head.next;  //作为下一个链表的头节点
        //找到中间节点,快指针走两步，慢指针走一步，快指针到了末尾的时候，慢指针的位置就是中间的位置
        while (fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            mid=mid.next;
        }
        //此时慢指针的位置就是中间节点的位置，mid就是第二个链表的头结点，便于右边部分划分链表
        // 需要断开指向，变成两个链表
        slow.next=null;
        return merge(sortInList(head),sortInList(mid));
    }
}
